package com.leetcode.array;

/**
 * Suppose a sorted array is rotated at some pivot
 *  unknown to you beforehand.
 *  (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 *  Find the minimum element.
 *  You may assume no duplicate exists in the array.
 * @author Adiy
 *
 */
public class FindMinimumRotatedSortedArray {

	public static void main(String[] args) {
		int nums[]={1,0};
		int left=0;
		int right=nums.length-1;
		int locality=findMin(nums);
		System.out.println(locality);
	}
	 public static int findMin(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		int mid = (left + right) / 2;

		while (mid > 0) {
			if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]) {
				return nums[mid];
			} else if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
				mid = mid + 1;
				return nums[mid];
			} else {
				if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]) {
					if (nums[mid] > nums[right]) {
						left = mid + 1;
						mid = (left + right) / 2;
						continue;
					} else {

						right = mid - 1;
						mid = (left + right) / 2;
						continue;
					}
				}
			}
		}
		  if(mid==0){
				if(nums[left]>=nums[right]){
					return nums[right];
				}else{
					return nums[left];
				}
			}
		return nums[mid];
	    
	 }
	
	
    public static int findMin(int[] nums,int left,int right) {
      int mid=(left+right)/2;
      
      while(mid>0){
    	   if(nums[mid]<nums[mid-1]&&nums[mid]<nums[mid+1]){
    	    	  return mid;  
    	      }else if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1]){
    	    	  mid=mid+1;
    	    	  return mid;
    	      }else{
    	    	  if(nums[mid]>nums[mid-1]&&nums[mid]<nums[mid+1]){
    	    		 if(nums[mid]>nums[right]){
    	    			 left=mid+1;
    	    			 mid=(left+right)/2;
    	    			 return findMin(nums,left,right);
    	    		 }else{
    	    		  
    	    		  right=mid-1;
    	    		  mid=(left+right)/2;
    	    		  return findMin(nums,left,right);
    	    		  }
    	    		 }
    	      }
      }
      if(mid==0){
			if(nums[left]>=nums[right]){
				return nums[right];
			}else{
				return nums[left];
			}
		}
     return mid;
    }
}
